//
// Created by Liming Shao on 11/6/2017.
//

#include "D187.h"
#include <iostream>

#define MIN(a,b) ((a)<(b)?(a):(b))
#define MAX(a,b) ((a)>(b)?(a):(b))

int D187::minPathSum(const vector<vector<int>> ma) {
    vector<vector<int> > sum(ma);
    sum[0][0] = ma[0][0];
    for (int i = 1; i < ma[0].size(); ++i) {
        sum[0][i] = sum[0][i-1] + ma[0][i];
    }

    for (int i = 1; i < ma.size(); ++i) {
        sum[i][0] = sum[i-1][0] + ma[i][0];
    }

    for (int i = 1; i < ma[0].size(); ++i) {
        for (int j = 1; j < ma.size(); ++j) {
            sum[i][j] = ma[i][j] + MIN(sum[i][j-1], sum[i-1][j]);
        }
    }

    return sum[sum.size()-1][sum[0].size()-1];
}

int D187::minPathSum2(const vector<vector<int> > ma) {
    int more = (int) MAX(ma.size(), ma[0].size());
    int less = (int) MIN(ma.size(), ma[0].size());
    bool rowmore = (more == ma.size()); // row > col
    int arr[less];
    arr[0] = ma[0][0];

    for (int i = 1; i < less; ++i) {
        arr[i] = arr[i-1] + (rowmore?ma[0][i]:ma[i][0]);
    }

    for (int i = 1; i < more; ++i) {
        arr[0] = arr[0] + (rowmore?ma[i][0]:ma[0][i]);
        for (int j = 1; j < less; ++j) {
            arr[j] = MIN(arr[j-1], arr[j]) + (rowmore?ma[i][j]:ma[j][i]);
        }
    }

    return arr[less-1];
}

void D187::test() {
    const vector<vector<int> > matirx({{1,3,5,9},{8,1,3,4},{5,0,6,1},{8,8,4,0}});
    cout << minPathSum2(matirx) << endl;
}